// https://www.lintcode.com/problem/spiral-matrix-ii/description?_from=ladder&&fromId=6

class Solution {
private:
    int step_x[4] = {0, 1, 0, -1};
    int step_y[4] = {1, 0, -1, 0}; // 注意x,y和(x, y)是反的
public:
    /**
     * @param n: An integer
     * @return: a square matrix
     */
    void fill(vector<vector<int>>& result, int x, int y, int dir, int val)
    {
        for (int i = 0; i < 4; ++i)
        {
            int j = (dir + i) % 4;
            int new_x = x + step_x[j];
            int new_y = y + step_y[j];
            if (new_x >= 0 && new_x < result.size() && new_y >= 0 && 
            new_y < result.size() && result[new_x][new_y] == 0)
            {
                result[new_x][new_y] = val;
                fill(result, new_x, new_y, j, val + 1);
            }
        }
    }
    vector<vector<int>> generateMatrix(int n) {
        
        vector<vector<int>> result(n, vector<int>(n, 0));
        fill(result, 0, -1, 0, 1); // 注意起始点(-1, 0)
        return result;
    }
};